1. 题目

统计所有小于非负整数 n 的质数的数量。

示例 1： 输入：n = 10 输出：4 解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

示例 2： 输入：n = 0 输出：0

示例 3： 输入：n = 1 输出：0

提示： $0 \leq n \leq 5 * 10^6$

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/count-primes 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题思路

没什么好说的，埃氏筛、线性筛（欧拉筛）

3. 代码

3.1. 埃氏筛

class Solution {
public:
    int countPrimes(int n) {
        int ans = 0;
        if(n<2) return ans;
        vector<int> isPrime(n+1,1);
        isPrime[0]=0, isPrime[1]=0;
        for(int i=2; i<n; ++i){
            if(isPrime[i]){
                ans++;
                if(1ll*i*i<=n)
                for(int j=i*i;j<=n;j+=i) isPrime[j] = 0; 
            }
        }
        return ans;
    }
};

3.2. 线性筛

class Solution {
public:
    int countPrimes(int n) {
        if(n<2) return 0;
        vector<int> isPrime(n+1,1);
        vector<int> primes;
        isPrime[0]=0, isPrime[1]=0;
        int ans;
        for(int i=2; i<n; ++i){
            if(isPrime[i]) primes.push_back(i);
            for(int j=0; j<primes.size() && i*primes[j]<=n; ++j ){
                isPrime[i*primes[j]] = 0;
                if(i%primes[j]==0) break;
            }
        }
        return primes.size();
    }
};